package org.example.algorithm;

import java.util.ArrayList;

/**
 * 寻找二叉树的最近公共祖先
 */
public class LowestCommonAncestorSolution {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5);
        treeNode.left = new TreeNode(3);
        treeNode.right = new TreeNode(2);
        TreeNode treeNodeFind = lowestCommonAncestor2(treeNode, treeNode, treeNode.right);
    }

    //此解法的前提是p或者q一定是root的节点
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);//遍历左子树，看是否找到最近公共祖先或者找到节点p或者q
        TreeNode right = lowestCommonAncestor(root.right, p, q);//遍历右子树，看是否找到最近公共祖先或者找到节点p或者q
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }

    public static TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        ArrayList<TreeNode> treeNodeArrayList1 = new ArrayList<>();
        ArrayList<TreeNode> treeNodeArrayList2 = new ArrayList<>();
        getPath(root, p, treeNodeArrayList1);
        getPath(root, q, treeNodeArrayList2);
        return getLastEqualNode(treeNodeArrayList1, treeNodeArrayList2);
    }

    //递归查找路径
    public static Boolean getPath(TreeNode root, TreeNode target, ArrayList<TreeNode> treeNodeArrayList) {
        treeNodeArrayList.add(root);
        if (root.equals(target)) {
            return true;
        }
        Boolean find = false;
        if (root.left != null) {
            if (getPath(root.left, target, treeNodeArrayList)) {
                return true;
            }
        }
        if (root.right != null) {
            if (getPath(root.right, target, treeNodeArrayList)) {
                return true;
            }
        }
        if (!find) {
            treeNodeArrayList.remove(treeNodeArrayList.size() - 1);
        }
        return find;
    }

    public static TreeNode getLastEqualNode(ArrayList<TreeNode> path1, ArrayList<TreeNode> path2) {
        int minSize = Math.min(path1.size(), path2.size());
        for (int i=0; i<minSize; i++) {
            if (!path1.get(i).equals(path2.get(i))) {
                return path1.get(i-1);
            }
        }
        return path1.get(minSize - 1);
    }
}
